題目連結: Middle of the Linked List

此題給定一非空且單向的 Linked List 及其 head，要我們返回中間節點，若此 Linked List 長度為偶數時，取兩中間節點的後者返回。

思路 1 : 遍歷法求長度

我們可以先找出該 linked list 長度為多少，再走一半路徑長即為中間節點所在。

• 複雜度評估
  當 Linked List 長度為 N 時，我們需要遍歷整個 Linked List，時間複雜度為 O(N)。
  此方法只使用了常數個變數，與 N 無關，空間複雜度為O(1)。

參考程式碼

func middleNode(head *ListNode) *ListNode {
    
    listNode := head
    l := 0
    for listNode != nil {
        l ++
        listNode = listNode.Next
    }
    
    listNode = head
    for i := 0; i < l/2; i ++ {
        listNode = listNode.Next
    }
    
    return listNode
}

思路 2 : 快慢指針法

我們可以仿造 day16-Linked List Cycle 提到的解法: 宣告兩個指針，慢的一次走一步，快的一次走兩步長。當快的指針走到終點時，慢指針剛好走到中間。需要留意的點為: 快指針一次走兩步長，我們要避免越界，以及當 Linked List 長度為偶數時，要取到正確的中間節點。

• 複雜度評估
  當 Linked List 長度為 N 時，我們需要遍歷整個 Linked List，時間複雜度為 O(N)。
  此方法只使用了常數個變數，與 N 無關，空間複雜度為O(1)。

參考程式碼

func middleNode(head *ListNode) *ListNode {
    
    slow, fast := head, head
    for fast != nil && fast.Next != nil { 
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

小結:

此題為快慢指針法的應用情境之一，LeetCode 上也有許多題可用此概念解。比快慢指針法更廣泛的概念為雙指針法，此時就不限定要宣告一快一慢的指針來遍歷某數據結構。

我將解法程式碼上傳到此，因為此題需要實作 ListNode，我尚未加上測試過程。